package nju.cs.ics.hooting.dp;
/**
 * 
 * @author Hooting<Hootingnju@gmail.com>
 *
 * Date:2013-9-7下午3:25:20
 * Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. 
 * Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want),
 *  or report that it's not possible to select coins in such a way that they sum up to S. 
 */

public class FindMinimumCoins {
	public static void main(String[] args) {
		int[] coins = new int[3];
		coins[0] = 1;
		coins[1] = 3;
		coins[2] = 5;
		getMin(coins, 3, 11);
		
	}
	public static int getMin(int[] coins, int N, int S){
		int[] min = new int[S+1];
		min[0] = 0;
		for (int i = 1; i<=S; i++){
			min[i] = S;
		}
		for (int i = 1; i <= S; i++){
			for (int j = 0; j < N; j++){
				if (coins[j] <= i){
					int temp = 1 + min[i-coins[j]];
					if ( temp < min[i]){
						min[i] = temp;
					}
				}
			}
		}
		for (int i = 0; i<=S; i++){
			System.out.printf("i=[%d] coins num=[%d]\n", i, min[i]);
		}
		return min[S];
	}

}
